package com.shuang.greed14;

import java.util.ArrayList;
import java.util.List;

public class PartitionLabels {
    //思路：
    //先记录字符串里每个字符出现位置的最远处
    //再遍历时 找到这一段字符位置最远处 并且当遍历的索引到达这个最远处时 就是这一段结束位置（这一段包含这个结束位置的数）
    public List<Integer> partitionLabels(String s) {
        //先将字符串转成字符数组操作
        char[] chars = s.toCharArray();

        //定义数组用来记录每个字符索引位置的最大值
        int[] edge = new int[26];

        //计算每个字符出现的索引最大值
        for (int i = 0; i < chars.length; i++){
            edge[chars[i] - 'a'] = i;
        }

        //用于更新每个片段的结束位置
        int last = -1; //初始化为 -1 因为i从零开始 第一段找到结束位置时 片段一共的字母数要加一

        //用于记录该片段中遇到的字符中 索引位置是最大的 （记录这个索引）
        int idx = 0;

        //存结果的集合
        List<Integer> res = new ArrayList<>();

        //再遍历字符数组 分段
        for (int i = 0; i < chars.length; i++){

            idx = Math.max(edge[chars[i] - 'a'], idx);

            if (i == idx){
                //遍历到这个字符的位置最远处时 就是该片段的结束索引位置
                res.add(i - last);

                //更新位置
                last = i;
            }
        }

        return res;
    }
}
